package com.example.demo.suanfa_jiegou;

/**
 * @program: java_base
 * @description: 使用 双端 node 实现 队列 和 栈 结构
 * @author: zhouhongtao
 * @happyCreateTime: 2022/02/10 09:23
 */
public class DoubleEndNode {

    public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        queue.offer(1);
        queue.offer(1);
        queue.offer(2);
        queue.offer(4);
//        System.out.println(1);
//        System.out.println(queue.poll());
//        System.out.println(queue.poll());
//        System.out.println(queue.poll());
//        System.out.println(queue.poll());

        ////////
        MyStack stack = new MyStack();
        stack.add(5);
        stack.add(6);
        stack.add(7);
        stack.add(8);
//        System.out.println(stack.pop());
//        System.out.println(stack.pop());
//        System.out.println(stack.pop());
//        System.out.println(stack.pop());
//        System.out.println(stack.pop());

        ZuoQueue queue1 = new ZuoQueue();
        queue1.push(10);
        queue1.push(20);
        queue1.push(30);
        queue1.push(40);
        System.out.println(queue1.pop());
        System.out.println(queue1.pop());
        System.out.println(queue1.pop());
        System.out.println(queue1.pop());
        System.out.println(queue1.pop());

        System.out.println("--------");

        ZuoStack stack1 = new ZuoStack();
        stack1.push(90);
        stack1.push(80);
        stack1.push(70);
        stack1.push(60);
        System.out.println(stack1.pop());
        System.out.println(stack1.pop());
        System.out.println(stack1.pop());
        System.out.println(stack1.pop());
        System.out.println(stack1.pop());
    }

    /**
     * 队列：逻辑数据结构
     * 可以使用：数组 / 双向节点 实现此逻辑结构
     * 队列结构特点：排队！顾名思义，先到先得 / 先进先出 / 后到后出
     * 经典作用：树结构 / 图结构 深度/广度 遍历 重要辅助作用
     * 基本方法： 入队 出队
     */
    static class MyQueue {
        //        private int value;
        private MyNode header;
        private MyNode tail;

        // 向队尾增加元素 入队 进入排队状态
        public void offer(int lastValue) {
            MyNode waitAppendNode = new MyNode(lastValue);
            if (header == null) {
                tail = waitAppendNode;
                header = waitAppendNode;
            } else {
                tail.next = waitAppendNode;
                waitAppendNode.pre = tail;
                tail = waitAppendNode;
            }
        }

        // 返回 队列 头部元素 并移动指针/删除队首元素/出队
        public int poll() {
            Object value = header.value;
            if (value != null) {
                MyNode next = header.next;
                if (next!=null){
                    next.pre = null;
                }
                header.next = null;
                header = next;
                return (int) value;
            } else {
                // throw new Exception()
                return -1;
            }
        }
    }


    /**
     * 一种逻辑结构
     * 栈结构的特性：先进入 后出  /  后进入的先出结构
     * 可以利用两个栈 实现队列结构
     * 还可以使用栈 实现树结构的深度/广度 遍历
     *
     */
    /////////

    /**
     * @author Frank
     */
    static class MyStack {
        private int value;
        private MyNode header;
        private MyNode tail;

        public void add(int addValue) {
            MyNode waitNode = new MyNode<>(addValue);
            if (header == null) {
                tail = waitNode;
                header = waitNode;
            } else {
                tail.next = waitNode;
                waitNode.pre = tail;
                tail = waitNode;
            }
        }

        public int pop() {
            if (tail == null) {
                // throw new Exception()
                return -1;
            }
            int popValue = (int) tail.value;
            tail = tail.pre;
            return popValue;
        }
    }

    static class MyNode<T> {
        public T value;
        public MyNode pre;
        public MyNode next;
        public MyNode(T value) {
            this.value = value;
        }
        @Override
        public String toString() {
            return "MyNode{" + "value=" + value + ", pre=" + pre + ", next=" + next + '}';
        }
    }

    ///////////// 以下为左老师代码 ///////////////////
    public static class Node<T>{
        public T value;
        public Node<T> last;
        public Node<T> next;
        public Node(T data) {
            value = data;
        }
    }

    ///////// *****  // 双向节点 类型 copy from zuochengyun
    /**
     * 使用 双向节点Node（双线链表） 将线性的的结构的操作全部封装
     * @param <T>
     */
    public static class DoubleEndsQueue<T> {
        public Node<T> head;
        public Node<T> tail;
        public void addFromHead(T value) {
            Node<T> cur = new Node<>(value);
            if (head == null){
                head = cur;
                tail = cur;
            } else{
                cur.next = head;
                head.last = cur;
                head = cur;
            }
        }

        public void addFromBottom(T value) {
            Node cur = new Node<>(value);
            if (head == null){
                head = cur;
                tail = cur;
            }else {
                // 将cur的上个指针接到上个 元素上
                cur.last = tail;
                // 将cur接尾巴上
                tail.next = cur;
                // 将tail变成cur
                tail = cur;
            }
        }

        public T popFromHead() {
            if (head == null){
                return null;
            }
            Node<T> cur = head;
            if (head == tail){
                head = null;
                tail = null;
            }else{
                // 指针移到下一个位点元素
                head = head.next;
                // 切断上个联系
                head.last = null;
                // 切断原head next 联系
                cur.next = null;
            }
            return cur.value;
        }

        public T popFromBottom() {
            if(tail == null){
                return null;
            }
            Node<T> cur = tail;
            if (head == tail ){
                head = null;
                tail = null;
            }else {
                tail = tail.last;
                cur.last = null;
                tail.next = null;
            }
            return cur.value;
        }
        public boolean isEmpty() {
            return head == null;
        }
    }

    public static class ZuoQueue<T> {
        private DoubleEndsQueue<T> queue;
        public ZuoQueue() {
            this.queue = new DoubleEndsQueue<>();
        }
        public void push(T value){
//            queue.addFromBottom(value);
            queue.addFromHead(value);
        }
        public T pop(){
//            return queue.popFromHead();
            return queue.popFromBottom();
        }
    }
    public static class ZuoStack<T> {
        private DoubleEndsQueue<T> stack ;
        public ZuoStack() {
            this.stack = new DoubleEndsQueue();
        }
        public void push(T value){
//            stack.addFromBottom(value);
            stack.addFromHead(value);
        }
        public T pop(){
//            return stack.popFromBottom();
            return stack.popFromHead();
        }
    }
}
